// https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked




// 时间复杂度(logm) * (logn)
// class Solution {
// public:
//     bool searchMatrix(vector<vector<int>>& matrix, int target) {
//         int row = matrix.size();
//         int col = matrix[0].size();
//         int lt = 0, rt = col - 1;
//         int index = 0;
//         while (lt <= rt) {
//             int mid = lt + (rt - lt)/2;
//             if (matrix[0][mid] > target) {
                
//                 rt = mid - 1;
//             } else if (matrix[0][mid] < target) {
//                 index = mid;
//                 lt = mid + 1;
//             } else {
//                 return true;
//             }
//         }
//         for (int i = 0; i <= index; i++) {
//             int l = 0, r = row - 1;
//             while (l <= r) {
//                 int mid = l + (r - l)/2;
//                 if (matrix[mid][i] > target) {
//                     r = mid - 1;
//                 } else if (matrix[mid][i] < target) {
//                     l = mid + 1;
//                 } else {
//                     return true;
//                 }
//             }
//         }
//         return false;
//     }
// };


// 最优解：从数组的右上角开始搜索值，类似二分的思路来查找的，也就是从右上角开始向左下角遍历
// 时间复杂度m + n;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            }
            else {
                ++x;
            }
        }
        return false;
    }
};

